package leetcodev1.数组;

import java.util.Arrays;

public class LeetCode45 {
    private int ret = Integer.MAX_VALUE;

    public static void main(String[] args) {
        LeetCode45 leetCode45 = new LeetCode45();
        int jump = leetCode45.jump(new int[]{2, 3, 1, 1, 4});
    }

    //动态规划
    //int[] dict 其中dict[i]意味着跳到第i个格子时最少的步数
    //dict[j] = dict[i]+1//前提dict[i]可以跳到j
    public int jump(int[] nums) {
        int[] dict = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            //应该从左到右遍历，满足条件后即可退出
            for (int j = 0; j < i; j++) {
                if (nums[j] >= i - j) {
                    dict[i] = dict[j] + 1;
                    break;
                }
            }
        }
        return dict[dict.length - 1];
    }

    public int jump1(int[] nums) {
        dfs(nums, 0, 0);
        return this.ret;
    }

    //超时
    //深度遍历 所有的树枝都遍历
    //广度遍历 todo
    private void dfs(int[] nums, int index, int step) {
        if (index == nums.length - 1) {
            this.ret = Math.min(this.ret, step);
            return;
        }

        if (index > nums.length - 1) {
            return;
        }

        //获取跳跃步数
        int num = nums[index];
        for (int i = 1; i <= num; i++) {
            dfs(nums, index + i, step + 1);
        }
    }

    public int jump2(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    public int jump3(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

}
